package 链表高频题和必备技巧;

/**
 * @author ljb
 * @version 1.0
 * @Date 2024/12/11
 */
// 每k个节点一组翻转链表
// 测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
public class Code02_ReverseNodesInkGroup {


    public class ListNode{
        public int val;
        public ListNode next;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode start = head;
        ListNode end = teamLinkEnd(start, k);
        if(end == null){
            return head;
        }
        // 第一组很特殊因为牵扯到换头的问题
        head = end;
        reverse(start, end);
        // 翻转之后start变成了上一组的结尾节点
        ListNode lastTeamEnd = start;
        while(lastTeamEnd.next != null){
            //新一组要翻转的头结点和尾结点
            start = lastTeamEnd.next;
            end = teamLinkEnd(start, k);
            //说明剩下的节点个数 < k，不能构成一个翻转组了
            if(end == null){
                return head;
            }
            reverse(start, end);
            //上一组翻转后的尾结点指向新翻转后的头结点
            lastTeamEnd.next = end;
            lastTeamEnd = start;
        }
        return head;
    }

    //返回要反转的这一组的尾结点
    public static ListNode teamLinkEnd(ListNode h, int k){
        while(--k != 0 && h != null){
            h = h.next;
        }
        return h;
    }

    // s -> a -> b -> c -> e -> 下一组的开始节点
    // 上面的链表通过如下的reverse方法调整成 : e -> c -> b -> a -> s -> 下一组的开始节点
    public static void reverse(ListNode s, ListNode e){
        //存储下一组的开始节点,以防断连
        e = e.next;
        ListNode pre = null, cur = s, next = null;
        while(cur != e){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        s.next = e;
    }
}
